#include <stdlib.h>
#include <stdio.h>
#include "bitree.h" //请不要删除，否则检查不通过

BiTNode* createBITNode(CSNode* csn) {
    if(!csn) return 0;
    BiTNode *res = malloc(20);
    res -> data = csn -> data;
    res -> left = res -> right = 0;
    return res;
}

BiTNode* transform(CSNode *root){
    // You need two queues instead of one queue of Pair.
    // Otherwise you'll find icoding saying queue being used wrongly.(And maybe a MLE attached)
    Queue *queue1 = create_queue(), *queue2 = create_queue();
    BiTNode *ans = createBITNode(root);
    add_queue(queue1, root);
    add_queue(queue2, ans);
    while(!is_empty_queue(queue1)) {
        CSNode *nd = del_queue(queue1);
        BiTNode *rt = del_queue(queue2), *pre;
        pre = rt -> left = createBITNode(nd -> children[0]);
        if(rt -> left) {
            add_queue(queue1, nd -> children[0]);
            add_queue(queue2, rt -> left);
        }
        for(int i=1;nd -> children[i];i++) {
            pre -> right = createBITNode(nd -> children[i]);
            add_queue(queue1, nd -> children[i]);
            add_queue(queue2, pre -> right);
            pre = pre -> right;
        }
    }    
    free_queue(queue1);free_queue(queue2);
    return ans;
}